package leetcode.weekly.week330;

//Solution4Test
public class Solution4 {

	public long countQuadruplets(int[] nums) {
		int[][] left = new int[nums.length][nums.length], right = new int[nums.length][nums.length];
		// left[i][j] 截至i-1位置小于j的数量
		for (int k = 0; k < nums.length; k++) {
			for (int i = 0; i < k; i++) {
				left[i + 1][k] = left[i][k] + (nums[i] < nums[k] ? 1 : 0);
			}
			for (int j = nums.length - 1; j > k; j--) {
				right[j - 1][k] = right[j][k] + (nums[j] > nums[k] ? 1 : 0);
			}
		}
		long count = 0;
//		0 <= i < j < k < l < n 且
		for (int j = 0; j < nums.length; j++) {
			for (int k = j + 1; k < nums.length; k++) {
				count += nums[j] > nums[k] ? left[j][k] * right[k][j] : 0;
			}
		}
		return count;
	}

}
